/**
 * 递归，不修改str，保证每次递归传下去的str的值不需要在删除
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis1 = function (n) {
  if (n === 1) return ["()"];
  let res = [];
  generateSub(n - 1, n, "(");

  function generateSub(li, ri, str) {
    if (ri <= 0) {
      res.push(str);
      return;
    }
    if (li === 0) {
      // 左括号枚举n次后，枚举右括号
      generateSub(li, ri - 1, str + ")");
    } else if (li === ri) {
      // 左括号的枚举次数必须大于右括号
      generateSub(li - 1, ri, str + "(");
    } else {
      // 否则，两种枚举都可以
      generateSub(li - 1, ri, str + "(");
      generateSub(li, ri - 1, str + ")");
    }
  }
  return res;
};

/**
 * 回溯，str的值被修改，后续回溯需要删除最后一位元素
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis2 = function (n) {
  if (n === 1) return ["()"];
  let res = [];
  generateSub(res, n, 0, 0, "");
  return res;
};

function generateSub(res, n, li, ri, str) {
  console.log(str, li, ri);
  if (str.length === n * 2) {
    res.push(str);
    return;
  }

  if (li < n) {
    str += "(";
    generateSub(res, n, li + 1, ri, str);
    str = str.slice(0, -1);
  }

  if (ri < li) {
    str += ")";
    generateSub(res, n, li, ri + 1, str);
    str = str.slice(0, -1);
  }
}
